package com.leetcode;

import com.leetcode.common.TreeNode;

/**
 * 235. 二叉搜索树的最近公共祖先
 * 深度优先搜索, 非递归写法
 *
 * @author fy
 * @date 2022/4/25 20:46
 */
public class Solution235_2 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p == null || q == null) {
            throw new RuntimeException("node p or q is null");
        }
        if (root == null) {
            return null;
        }
        TreeNode node = root;
        // 这种方法也有一个前提就是, p和q都在树中
        while (node != null) {
            if (node.val > p.val && node.val > q.val) {
                node = node.left;
            } else if (node.val < p.val && node.val < q.val) {
                node = node.right;
            } else {
                return node;
            }
        }
        return null;
    }

}
